home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 181_01 / commlzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1985-03-09  |  6.8 KB  |  225 lines
  1. /* COMMLZW - ROUTINES COMMON TO LZWCOM AND LZWUNC                       */
  2. #include "stdio.h"
  3. #include "debug.h"
  4. #define FALSE    0
  5. #define TRUE     !FALSE
  6. #define TABSIZE  4096
  7. #define NO_PRED  0xFFFF
  8. #define EMPTY    0xFFFF
  9. #define NOT_FND  0xFFFF
  10. #define SECTSIZE 128
  11. #define CTRLZ '\032' /* ascii end of file */
  12. extern struct entry {
  13.   char used;
  14.   unsigned int next;                    /* index of next in collision list */
  15.   unsigned int predecessor;             /* 12 bit code                  */
  16.   unsigned char follower;
  17. } string_tab[TABSIZE];
  18.  
  19. extern char is_a_con;
  20. /* h uses the 'mid-square' algorithm. I.E. for a hash val of n bits     */
  21. /* hash = middle binary digits of (key * key).  Upon collision, hash    */
  22. /* searches down linked list of keys that hashed to that key already.   */
  23. /* It will NOT notice if the table is full. This must be handled        */
  24. /* elsewhere                                                            */
  25.  
  26. unsigned h(pred,foll)
  27. /* returns the mid square of pred + foll                                */
  28.     unsigned int pred; unsigned char foll;
  29. {
  30.   long temp, local;             /* 32 bit receiving field for local^2   */
  31.   local = (pred + foll) | 0x0800;
  32.   temp = local * local;
  33.   local = (temp >> 6) & 0x0FFF;
  34.   return local;                 /* middle 12 bits of result             */
  35. }
  36.  
  37. unsigned eolist(index)
  38. /* return last element in a collision list                              */
  39. unsigned int index;
  40. {
  41.   register int temp;
  42.   while ( 0 != (temp = string_tab[index].next) )
  43.     index = temp;
  44.   return index;
  45. }
  46.  
  47. unsigned hash(pred,foll,update)
  48. unsigned int pred; unsigned char foll; int update;
  49. {
  50.   register unsigned int local, tempnext;
  51.   register struct entry *ep;
  52.   local = h(pred,foll);
  53.   if ( !string_tab[local].used )
  54.     return local;
  55.   else {
  56.   /* if collision has occured                                           */
  57.     local = eolist(local);
  58.  
  59.   /* search for free entry from local + 101 */
  60.     tempnext = (local + 101) & 0x0FFF; 
  61.     ep = &string_tab[tempnext];                 /* initialize pointer   */
  62.     while ( ep->used ) {
  63.       ++tempnext;
  64.       if ( tempnext == TABSIZE ) {
  65.         tempnext = 0;           /* handle wrap to beginning of table    */
  66.         ep = string_tab;        /* address of first element of table    */
  67.       } else
  68.         ++ep;                   /* point to next element in table       */
  69.     }
  70.     
  71.     /* put new tempnext into last element in collision list             */ 
  72.     if ( update )               /* if update requested                  */
  73.       string_tab[local].next = tempnext;
  74.     return tempnext;
  75.   } 
  76. }
  77.  
  78. /* unhash uses the 'next' field to go down the collision tree to find   */
  79. /* the entry corresponding to the passed key                            */
  80. /* passed key and returns either the matching entry # or NOT_FND        */
  81.  
  82. unsigned unhash(pred,foll)
  83. unsigned int pred; unsigned char foll;
  84. {
  85.   register unsigned int local, offset;
  86.   register struct entry *ep;    /* pointer to current entry             */
  87.  
  88.   local = h(pred,foll);         /* initial hash                         */
  89.   loop:
  90.     ep = &string_tab[local];
  91.     if ( (ep->predecessor == pred) && (ep->follower == foll) ) 
  92.       return local;
  93.     if ( ep->next == 0 )
  94.       return NOT_FND;
  95.     local = ep->next;
  96.   goto loop;
  97. }
  98.  
  99. init_tab() {
  100.   register unsigned int i;
  101.   setmem((char *)string_tab,sizeof(string_tab),0);
  102.   for (i = 0; i <= 255; i++) {
  103.     upd_tab(NO_PRED,i);
  104.   }
  105. }
  106.  
  107. #define UPDATE TRUE
  108.  
  109. upd_tab(pred,foll)
  110.   unsigned int pred, foll;
  111. {
  112.   register struct entry *ep;    /* pointer to current entry     */
  113.   /* calculate offset just once */
  114.   ep = &string_tab[ hash(pred,foll,UPDATE) ];
  115.   ep->used = TRUE;
  116.   ep->next = 0;
  117.   ep->predecessor = pred;
  118.   ep->follower = foll;
  119. }
  120.  
  121.  
  122. unsigned int inbuf = EMPTY;
  123. unsigned int outbuf = EMPTY;
  124.  
  125. /* getcode and putcode 'gallop' through input and output - they either  */
  126. /* output two bytes or one depending on the contents of the buffer.     */
  127.  
  128. getcode(fd) 
  129. int fd;     {
  130.   register unsigned int localbuf, returnval;
  131.   if (EMPTY == inbuf) {         /* On code boundary                     */
  132.     if (EOF == (localbuf = readc(fd)) ) {       
  133.                                 /* H L1 byte - on code boundary         */
  134.       return EOF;
  135.     }
  136.     localbuf &= 0xFF;
  137.     if (EOF == (inbuf = readc(fd)) ) {  /* L0 Hnext                     */
  138.       return EOF;       /* The file should always end on code boundary  */
  139.     }
  140.     inbuf &= 0xFF;
  141.     DEBUGGER(fprintf(stderr,"%x and %x read\n",localbuf,inbuf);)
  142.     returnval = ((localbuf << 4) & 0xFF0) + ((inbuf >> 4) & 0x00F);
  143.     DEBUGGER(fprintf(stderr,"returnval = %x\n",returnval);)
  144.     inbuf &= 0x000F;
  145.   } else {                      /* buffer contains nibble H             */
  146.     if (EOF == (localbuf = readc(fd)) )
  147.       return EOF;
  148.     localbuf &= 0xFF;
  149.     DEBUGGER(fprintf(stderr,"%x read, inbuf = %x\n",localbuf,inbuf);)
  150.     returnval = localbuf + ((inbuf << 8) & 0xF00);
  151.     inbuf = EMPTY;
  152.     DEBUGGER(fprintf(stderr,"returnval = %x\n",returnval);)
  153.   }
  154.   return returnval;
  155. }
  156.  
  157. putcode(fd,code)
  158. unsigned int fd,code;     {
  159.   register int localbuf;
  160.   if (EMPTY == outbuf) {
  161.     writec( fd,((code >> 4) & 0xFF));    /* H L1                        */
  162.     outbuf = code & 0x000F;     /* L0                                   */
  163.   } else {
  164.     writec( fd, ( ((outbuf << 4) & 0xFF0) + ((code >> 8) & 0x00F) ) );
  165.                                 /* L0prev H                             */
  166.     writec( fd,(code & 0x00FF));        /* L1 L0                        */
  167.     outbuf = EMPTY;
  168.   }
  169. }
  170.  
  171.  
  172. int limit;
  173. char insector[SECTSIZE];
  174. int current = 0;
  175. int sector = 0;
  176. readc(fd)
  177. int fd;
  178. {
  179.   register int returnval;
  180.   if (current == 0) 
  181.   {
  182.     if ( 0 == (limit = read(fd,insector,SECTSIZE)) ) 
  183.     {
  184.       return (EOF);
  185.     } else 
  186.     {
  187.       if (!is_a_con)
  188.         if ( (++sector % 80) )
  189.           putchar('.');
  190.         else 
  191.         {
  192.           putchar('.');
  193.           putchar('\n');
  194.         }
  195.     }
  196.   }
  197.   returnval = (insector[current++]);
  198.   if (current == limit) {
  199.     current = 0;
  200.   }
  201.   return (returnval & 0xFF);
  202. }
  203.  
  204. char outsector[SECTSIZE];
  205. int outcurrent = 0;
  206.  
  207. writec(fd,c)
  208. int fd,c;   {
  209.   outsector[outcurrent++] = ( (char) c);
  210.   if (outcurrent == SECTSIZE) {
  211.     outcurrent = 0;
  212.     write(fd,outsector,SECTSIZE);
  213.   }   
  214. }
  215.  
  216. /* flushout makes sure fractional output buffer gets written */
  217. flushout(fd)
  218. int fd; {
  219.   if (EMPTY != outbuf)    /* if there's still a byte waiting to be packed */
  220.                         /* stuff it in the buffer */
  221.     outsector[outcurrent++] = (outbuf << 4) & 0xFF0;    
  222.   DEBUGGER(fprintf(stderr,"\nflushout - writing %d bytes\n",outcurrent);)
  223.   write(fd,outsector,outcurrent);
  224. }
  225.